/*
 * =====================================================================================
 *
 *       Filename:  numOneCount.c
 *
 *    Description:  given n, caculate the occurence count of '1' from 1 to n
 *
 *        Version:  1.0
 *        Created:  2012年03月29日 15时30分26秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:  
 *
 * =====================================================================================
 */

#include	"utility.h"

//从低往高算难算,bad idea
int getOneCnt(int n)
{
    int cnt = 0;
    int m = abs(n);
    int todevide = 1;
    int toadd;
    while (m/todevide)
    {
        int devided = todevide * 10;
        int remain = (m % devided) / todevide;
        int remainremain = (m % todevide);
        int x = m / devided;
        if (remain == 1)
            toadd = x * todevide + (remainremain + 1);
        else if (remain > 1)
            toadd = (x+1) * todevide;
        else
            toadd = x * todevide;
        cnt += toadd;
        todevide = devided;
    }
    return cnt;
}

int caculateOneCnt(int n)
{
    int cnt = 0;
    while (n)
    {
        if (n % 10 == 1)
            ++cnt;
        n /= 10;
    }
    return cnt;
}

//写个离线算法进行测试
int test()
{
    int storedvalue[65536];
    storedvalue[0] = 0;
    int k ;
    for (k = 1; k < 65536; ++k)
    {
        int oneCntThisNum = caculateOneCnt(k);
        storedvalue[k] = oneCntThisNum + storedvalue[k-1];
        int res = getOneCnt(k);
        printf ( "value:%d, stored:%d, caculated:%d\n", k, storedvalue[k], res );
        assert(storedvalue[k] == res); 
    }
    return 0;
}

int main(int argc, char *argv[])
{
    test();
    return 0;
}
